package com.hanxiaozhang.no10leetcode.array;

/**
 * 〈一句话功能简述〉<br>
 * 〈最佳时间买入卖出股票〉
 * 给定一个数组，数组中的元素i代表了第i天的股票价格。
 * 在只允许进行一次交易的情况下，设计一个算法计算出最大收益。
 * 实例1:
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解析:第2天买入（价格=1），第5天卖出（价格=6），利润=6-1=5。不是7-1=6，因为卖出价格需要大于买入价格。
 * <p>
 * 实例2:
 * 输入: [7,6,4,3,1]
 * 输出: 0
 * 解析：在这种情况下，不进行任何交易，即最大利润=0
 * <p>
 * 思路：方法2
 * 特点：
 * 1.买股票有利润，一定是低买高卖。
 * 2.数组中记录从第一天到最后一天的价格信息。
 * 通过以上两点可以推论出来：最小值（最低价格）在数组前边，最大值在数组在数组后边，才有利润。
 * --> 即：一个循环，选获取最小，再计算最大利润
 *
 * @author hanxinghua
 * @create 2024/1/26
 * @since 1.0.0
 */
public class No121BestTimeTradeStock {


    public static void main(String[] args) {

        int[] arr1 = {7, 1, 5, 3, 6, 4};

        int[] arr2 = {7, 6, 4, 3, 1};

        System.out.println(method1(arr1));
        System.out.println(method2(arr1));


    }

    /**
     * 方法2
     * <p>
     * 特点：
     * 1.买股票有利润，一定是低买高卖。
     * 2.数组中记录从第一天到最后一天的价格信息。
     * 通过以上两点可以推论出来：最小值（最低价格）在数组前边，最大值在数组在数组后边，才有利润。
     * --> 即：一个循环，选获取最小，再计算最大利润
     *
     * @param arr
     * @return
     */
    private static int method2(int[] arr) {

        // 利润最大值
        int profitMax = 0;
        if (arr == null || arr.length < 2) {
            return profitMax;
        }

        // 记录股票最低价格
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min, arr[i]);
            profitMax = Math.max(profitMax, arr[i] - min);
        }
        return profitMax;
    }


    /**
     * 方法1
     *
     * @param arr
     * @return
     */
    private static int method1(int[] arr) {

        int max = 0;
        if (arr == null || arr.length < 2) {
            return max;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    max = Math.max(max, arr[j] - arr[i]);
                }
            }
        }
        return max;
    }


}
